Section: Research Program

Recent results and ongoing work

Theoretical work by Meunier and Woods “The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation” was published in 2017 at the conference STOC, Montreal, Canada, and later presented as a poster and chosen for a short oral talk at DNA23, UT Austin, TX, USA, (presentations by Meunier). In this model, called the noncooperative (or temperature 1) abstract Tile Assembly Model, square tiles assemble into structures in the discrete plane (${\mathbb{Z}}^2$) where each tile binds to a growing structure if one of its 4 coloured edges matches the colour of some available edge on the growing structure. It has been conjectured since 2000 that this model is not capable of computation or other sophisticated forms of growth. We show two results. One of our results states that time-bounded Turing machine computation is impossible in this model if we require the simulation to occur in a bounded rectangle in the plane. This result has a short proof that essentially follows from our other main result (with a more involved prof) which states that this model is not “intrinsically universal”. This latter result means that there is no single tileset in this model that can simulate any instance of the model, answering a question from [Meunier, Patitz, Summers, Theyssier, Winslow, Woods; SODA 2014] and contrasting a result [Doty, Lutz, Patitz, Schweller, Summers, Woods; FOCS 2012] for the more general cooperative (temperature 2) model.

A number of popular models of computation for molecular computing are kinetic in nature: the rules of the systems describe how system evolves, step-by-step over time. However, such models allow one to program structures and behaviours that contradict how molecular systems would behave on long enough (e.g. infinite) time-scales. Recently, Doty, Rogers, Soloveichik, Thachuk and Woods proposed a thermodynamic based model called Thermodynamic Binding Networks. One programs the model by specifying a multiset of molecules, and then the 'output' is defined as the (or a, if many) multiset of polymers deemed most 'thermodynamically stable' out of all possible multisets of polymers definable in the model. In order to clarify the roles of fundamental thermodynamic concepts in molecular computing, the model makes a number of simplifying assumptions including a lack of geometry and (essentially) an infinite biasing of enthalpy over entropy. This model was published at the DNA23 conference at the University of Texas at Austin in 2017, along with some results: The authors show how to program the model to evaluate Boolean AND/OR formulas, and how to efficiently self-assemble simple structures (a binary counter), Also, limitations (upper bounds) on the size of objects self-assemblable are shown. It is hoped this work will lead to new ways of thinking about computation with molecules.

In experimental work, Thubagere, Li, Johnson, Chen, Doroudi, Lee, Izatt, Wittman, Srinivas, Woods, Winfree and Qian, implemented a molecular walker made out of DNA. The walker randomly around on a 2D nanoscale testing ground, picking up one of two types of cargos (also DNA molecules) and dropping them off at specific goal locations. The work shows the power of simple randomised algorithms in molecular systems. This work was led by Thubagary and Qian at Caltech; Woods' contribution occurred while at Caltech (before joining Inria). The work was published in Science.

Experimental work by Woods and collaborators Doty, Myhrvold, Hui, Zhou, Yin and Winfree has focused on experimentally implementing a wide class of Boolean circuits of a certain form. Experiments were mostly carried out at Caltech, with data analysis and paper writeup being carried out a Inria, UC Davis and Caltech. A publication is in preparation.

ENS student Tristan Stérin is leading theoretical work on analysing the computational power of the previously mentioned iterated Boolean circuit model of Woods, Doty, Myhrvold, Hui, Zhou, Yin, Winfree. Preliminary results were presented as a poster at DNA23 (UT Austin, TX, USA) where Tristan won “DNA23 best poster award”. The work is in preparation for a conference publication.

There are a number of ongoing projects along the lines of topics above in Overall Objectives.